import java.util.Arrays;

public class PriorityQueue {

        public int[] elem;
        public int usedSize;

        public PriorityQueue() {
                this.elem = new int[10];
        }

        public void InitElem(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        elem[i] = array[i];
                        usedSize++;
                }
        }
        /**
         * 建堆的时间复杂度：
         *
         * @param
         */
        public void createHeap() {
                for (int i = (usedSize - 2) / 2; i >= 0; i--) {
                        shiftDown(i,usedSize);
                }
        }

        /**
         *
         * @param parent 是每棵子树的根节点的下标
         * @param len  是每棵子树调整结束的结束条件
         * 向下调整的时间复杂度：O(logn)
         */
        private void shiftDown(int parent,int len) {
                int child = parent*2+1;
                while(child < len) {
                        if(child + 1 < usedSize&&elem[child] < elem[child + 1]) {
                                child++;
                        }
                        if(elem[child] > elem[parent]) {
                                Swap(elem,child,parent);
                                parent = child;
                                child = parent * 2 + 1;
                        }else {
                                break;
                        }
                }
        }


        /**
         * 入队：仍然要保持是大根堆
         * @param val
         */
        public void push(int val) {
                if(isFull()) {
                        elem = Arrays.copyOf(elem,2 * elem.length);
                }
                this.elem[usedSize] = val;
                shiftUp(usedSize);
                usedSize++;
        }


        public void Swap(int[] elem,int i,int j) {
                int tmp = elem[i];
                elem[i] = elem[j];
                elem[j] = tmp;
        }

        private void shiftUp(int child) {
                int parent = (child - 1) / 2;
                while(parent >= 0) {
                        if(elem[child] > elem[parent]) {
                                Swap(elem,child,parent);
                                child = parent;
                                parent = (child - 1) / 2;
                        }
                        else {
                                break;
                        }
                }
        }

        public boolean isFull() {
                return this.usedSize == this.elem.length;
        }

        /**
         * 出队【删除】：每次删除的都是优先级高的元素
         * 仍然要保持是大根堆
         */
        public int pollHeap() {
                int ret = elem[0];
                Swap(elem,0,usedSize - 1);
                usedSize--;
                shiftDown(0,usedSize);
                return ret;
        }

        public boolean isEmpty() {
                return usedSize == 0;
        }

        /**
         * 获取堆顶元素
         * @return
         */
        public int peekHeap() {
                if(isEmpty()) {
                        return -1;
                }
                return elem[0];
        }
}
